Bootstrapping usually refers to the process of loading basic software into a memory of a computer after power-on or general reset, especially an operating system which will then take care of loading other software as needed. Bootstrapping is an important procedure to assessing secure environments. Whenever some security mechanism is executed, the trustful execution of all processes has to be ensured until the execution of the security mechanism happens. A trustful execution of processes is referred to as secure bootstrapping. Otherwise, a malicious process nested in the execution chain may annul the security mechanism in question and harm the system. For instance, a malicious boot loader—the BIOS does not know the difference between a malicious and a trusted boot loader, so it allows either to boot—can hijack the boot routine and conceal malicious processes from the operating system. Such a loader can suppress any off-the-shelf security mechanism and render a secure execution environment void.
There are many techniques or methods to assess a secure bootstrapping in computing environments, ranging from hardware to software-based solutions on different nodes of the execution chain, where probably TPMs are settled on the lowest layer and anti-virus software on the highest layer. In particular the initialization of secure bootstrapping is important. By initialization the stage of creating an environment is meant, which is assumed to be free from any malicious process. A system in this stage is called to be in the zero-state. If a system is bootstrapped from the zero-state, strong guarantees regarding the reliability and trustworthiness of executed processes and software are attained. A trusted computing environment can then be built on top of a chain of secure bootstrapping mechanisms.
To eliminate malicious code one can wipe out the memory (or any other persistent storage). Wipe-outs, i.e. the process of erasing data from a device, can be performed remotely and have become an essential ingredient in the security management of devices, such as smart devices and clouds, not only because they facilitate a secure installation of firmware, operating systems, and applications, but also because they often contain sensitive business data, including personally identifiable information of employees and customers, sensitive email messages, and other items. When a device is infected, lost, or stolen the potential security risk can be significant. Remote wipe-outs are the last resort to assess the confidentiality of data.
To address the problem of secure wipe outs one could use a small trusted module (e.g. tiny TPM) that halts all system processes, accesses the memory independently of the central processing unit, and overwrites the memory with ‘1’s. Conventional methods and systems are for example disclosed in the non patent literature of Patrick Koeberl, Steffen Schulz, Ahmad-Reza Sadeghi, and Vijay Varadharajan. Trustlite: a security architecture for tiny embedded devices. In Dick C. A. Bulterman, Herbert Bos, Antony I. T. Rowstron, and Peter Druschel, editors, Ninth Eurosys Conference 2014, EuroSys 2014, Amsterdam, The Netherlands, Apr. 13-16, 2014, page 10. ACM, 2014. However, additional hardware is expensive and not applicable to all settings. Nowadays conventional off-the-shelf device management tools support software-based remote wipe-outs. Unfortunately, the underlying mechanisms give no guarantees that the deletion has indeed taken place. An adversary in control of the device might intercept the wipe-out request and fake the response. Thus, the user is left with the unsatisfying situation of trusting the device.
Conventional cryptographic proofs exist for various time problems for example disclosed in the non-patent literature of Oded Goldreich. Foundations of Cryptography: Basic Tools. Cambridge University Press, New York, N.Y., USA, 2000. Specifically, proof systems for languages that are decidable in polynomial space on a deterministic Turing machine are known as Proofs of Space (PoS), and have been disclosed e.g. in the non-patent literature of Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. Cryptology ePrint Archive, Report 2013/796, 2013. http://eprint.iacr.org/. or in the non-patent literature of Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, and Nicola Galesi. Proofs of space: When space is of the essence. In Abdalla and Prisco Security and Cryptography for Networks—9th International Conference, SCN 2014, Amalfi, Italy, Sep. 3-5, 2014. Proceedings, volume 8642 of Lecture Notes in Computer Science (Springer, 2014), pages 538-557. In a PoS a prover convinces a verifier of the fact that it dedicated some space O(S), where S is the size of memory (polynomial in the security parameter), and her odds to consume in fact less space are negligible. In said non-patent literature of Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. Cryptology ePrint Archive, Report 2013/796, 2013. http://eprint.iacr.org/ an application to online polling and the bitcoin payment system is shown.
In the non-patent literature of Daniele Perito and Gene Tsudik. Secure code update for embedded devices via proofs of secure erasure. In ESORICS, pages 643-662, 2010 PoS for provably secure wipe-outs is shown. In said non-patent literature a construction in which the verifier communicates a string of length S, and obtains a proof in form of a hashed MAC over string is described. One of the problems is that the method becomes impractical with growing S, e.g. considering a cloud with some terabytes storage capacity.
A method with reduced complexity to an order sublinear in the size of S is shown in the non-patent literature of Stefan Dziembowski, Sebastian Faust, Vladimir Kolmogorov, and Krzysztof Pietrzak. Proofs of space. Cryptology ePrint Archive, Report 2013/796, 2013. http://eprint.iacr.org/. Said method is based on graph pebbling, a technique introduced in the non-patent literature of Cynthia Dwork, Moni Naor, and Hoeteck Wee. Pebbling and proofs of work. In Victor Shoup, editor, Advances in Cryptology—CRYPTO 2005: 25th Annual International Cryptology Conference, Santa Barbara, Calif., USA, Aug. 14-18, 2005, Proceedings, volume 3621 of Lecture Notes in Computer Science, pages 37-54. Springer, 2005. The communication complexity is minimized to O(log S), but requires a preprocessing in which the prover and verifier allocate space O(S) and O(log S), respectively.
In the non-patent literature of Nikolaos P. Karvelas and Aggelos Kiayias. Efficient proofs of secure erasure. In Abdalla and Prisco Security and Cryptography for Networks—9th International Conference, SCN 2014, Amalfi, Italy, Sep. 3-5, 2014. Proceedings, volume 8642 of Lecture Notes in Computer Science (Springer, 2014), pages 520-537 a variant of the pebbling game with a storage complexity O(S) in the preproccesing is described, but where the verifier needs to reserve S(1) in the online phase. In the non-patent literature of Giuseppe Ateniese, Ilario Bonacina, Antonio Faonio, and Nicola Galesi. Proofs of space: When space is of the essence. In Abdalla and Prisco Security and Cryptography for Networks—9th International Conference, SCN 2014, Amalfi, Italy, Sep. 3-5, 2014. Proceedings, volume 8642 of Lecture Notes in Computer Science (Springer, 2014), pages 538-557. a variant of the pebbling game with O(1) verifier storage complexity is described. However said method requires the verifier to seize O(log S) space in the online phase.